package com.atcumt.Carl.Dfs;

public class Dfs04 {

    /**
     * 解数独
     */
    public void solveSudoku(char[][] board) {
        SuduHelper(board, 0, 0);
    }

    private boolean SuduHelper(char[][] board, int row, int col) {
        if (col == 9) {
            return SuduHelper(board, row + 1, 0); // 到该行末尾之后, 换到下一行重新开始
        }
        if (row == 9) {
            return true; // 终止条件
        }

        if (board[row][col] != '.') {
            return SuduHelper(board, row, col + 1);
        }

        for (char c = '1'; c <= '9'; c++) {
            if (!isValid(board, row, col, c)) {
                continue;
            }

            board[row][col] = c;
            if (SuduHelper(board, row, col + 1)){
                return true;
            }
            board[row][col] = '.';
        }
        return false;
    }

    private boolean isValid(char[][] board, int row, int col, char c) {
        for (int i = 0; i < 9; i++) {

            if (board[row][i] == c) {
                return false; // 同一行无冲突
            }

            if (board[i][col] == c) {
                return false; // 同一列无冲突
            }

            if (board[(row / 3 * 3 + i / 3)][(col / 3) * 3 + i % 3] == c) {
                return false; // 九宫格无冲突
            }
        }
        return true;
    }

}
